#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

class Solution:
    """
    @param l1: the first list
    @param l2: the second list
    @return: the sum list of l1 and l2
    """
    def addLists(self, l1, l2):
        carry = 0
        dummy_head = num_tail = ListNode('dummy')

        now_1, now_2 = l1, l2

        # process two node
        while now_1 and now_2:
            value = now_1.val + now_2.val + carry
            carry, remain = self.carry_remain(value)
            num_tail = self.push_tail(num_tail, remain)
            now_1, now_2 = now_1.next, now_2.next

        single_now = now_1 or now_2

        # process single_now
        while single_now:
            if carry == 0:
                # 没有carry, 只剩一个链表. 直接把链表追加
                num_tail.next = single_now
                break
            value = carry + single_now.val
            carry, remain = self.carry_remain(value)
            num_tail = self.push_tail(num_tail, remain)
            single_now = single_now.next

        if carry:
            # 处理single_now 完了, 还剩个carry情况
            assert single_now is None
            self.push_tail(num_tail, carry)

        return dummy_head.next

    def push_tail(self, tail, value):
        # return new tail
        assert value < 10
        new_node = ListNode(value)
        tail.next = new_node
        # num_tail = new_node
        return new_node

    def carry_remain(self, value):
        carry = value // 10
        remain = value % 10
        return carry, remain

def show(n):
    while n:
        print("%s ----> " % n.val, sep=' ', end=' ')
        n = n.next
    print()


def main():
    print("start main")
    s = Solution()

    v5 = ListNode(5)
    v4 = ListNode(4, v5)
    v3 = ListNode(10, v4)
    v2 = ListNode(2, v3)
    v1 = ListNode(2, v2)
    v0 = ListNode(2, v1)
    # vm = ListNode(100, v0)

    ret = s.addLists(v0, v0)
    show(ret)

if __name__ == "__main__":
    main()
